package com.xy6.algo.search;

import java.util.Arrays;

/**
 * 分块查找
 * <p>时间复杂度：O(log2^n)
 * <p>适用于有序的、静态集合
 * <p>顺序查找的改进版，与顺序查找相比，性能有较大提升。本质与二分查找相同。
 * 
 * <pre>
 * 待查找元素为x；
 * 将n个元素分为m个块；
 * 取每块第一个元素的索引，及最后一个元素的索引，组合为一张索引表；
 * 将x顺序与索引表中元素进行比较，找到第一个比x大的元素i，则x在的i的前一个块上；
 * 对块上元素顺序查找，与x进行比较，得到x的索引；
 * </pre>
 * 
 * @author zhang
 * @since 2017-08-24
 */
public class SearchBlock {

	public static void main(String[] args){
		Integer[] arr = new Integer[] { 1, 2, 3, 5, 6, 10, 50, 100 };
		int index = search(arr, 3, 400);
		System.out.println(index);
	}
	
	public static int search(Integer[] arr, int n, int val) {
		// 将集合分为m组，每组n个元素
		int m = Double.valueOf(Math.ceil(arr.length * 1.0 / n)).intValue();
		Integer[] indexs = new Integer[m + 1];
		int count = 0;
		// 第x组，首尾元素
		for (int i = 0; i < m; i++) {
			int first = n * i;
			indexs[count++] = first;
		}
		indexs[count] = arr.length - 1;
		System.out.println(Arrays.toString(indexs));
		
		// TODO 对indexs进行二分查找
		if(arr[indexs[0]] > val){
			return -1;
		} else if(arr[indexs[indexs.length - 1]] < val){
			return -1;
		}
		int end = -1;
		for (int i = 0; i < indexs.length; i++) {
			if(arr[indexs[i]] >= val){
				end = i;
				break;
			}
		}
		int begin = end-1 >= 0 ? end-1 : 0;
		for (int j = indexs[begin]; j <= indexs[end]; j++) {
			if (arr[j] == val) {
				return j;
			}
		}
		return -1;
	}
	
}
